package tosp.search;

import org.apache.log4j.Logger;

import tosp.HistoryMachine;
import tosp.JobSequence;

public abstract class LocalSearchAdapter {
	
	static Logger log = Logger.getLogger(LocalSearchAdapter.class);
	HistoryMachine start;
	int steps=0, visitedNeighbors=0;

	
	public LocalSearchAdapter(HistoryMachine m) {
		start=m;
	}

	/**
	 * Gibt die Anzahl der Iterationen an.
	 * @return
	 */
	public int getStepCounter() {
		return steps;
	}
	
	/**
	 * Gibt die Anzahl der untersuchten Nachbarn an
	 * @return
	 */
	public int getVisitedNeighbourCounter() {
		return visitedNeighbors;
	}
	
	
	/**
	 * Default: Break if no improvement after 100 iterations
	 */
	private int noImpCounter=0;
	private boolean breakCriteria(boolean improvement, int limit) {
		if (improvement) noImpCounter=0; 
		else noImpCounter++;
		return noImpCounter>limit;
	}
	
	/**
	 * If you don't override this, it will call getNeighbors
	 * @param j
	 * @param index
	 * @return
	 */
	private JobSequence[] cache=null;
	private JobSequence cacheJob=null;
	public JobSequence getNeighbor(JobSequence j,int index) {
		if (cacheJob==j) {
			if (index<cache.length) return cache[index];
			else return null;
		} else {
			cacheJob=j;
			cache=getNeighbors(j);
			if (index<cache.length) return cache[index];
			else return null;
		}
	}
	
	public int getNeighborSize(JobSequence j) {
		if (cacheJob!=j) {
			cacheJob=j;
			cache=getNeighbors(j);
		}
		return cache.length;
	}
	
	/**
	 * If you dont override getNeighbor() you have to override this.
	 * @param j
	 * @return
	 */
	abstract protected JobSequence[] getNeighbors(JobSequence j);

	
	
	/**
	 * Next improvement Search
	 * @return
	 */
	public JobSequence nextImprovementSearch() {
		JobSequence j=start.jobSeq;
		int bestToolSwitches=start.getToolSwitches();
		boolean improvement=true;
		
		while (!breakCriteria(improvement,1)) {
			int i=0;
			steps++;
			JobSequence n;
			improvement=false;
			while ((n=getNeighbor(j, i))!=null ) {
				HistoryMachine m=new HistoryMachine(n);
				visitedNeighbors++;
				if (m.getToolSwitches()<bestToolSwitches) {
					bestToolSwitches=m.getToolSwitches();
					j=m.jobSeq;
					improvement=true;
					break;
				}
				i++;
			}
		}
		return j;
	}
	
	
	/**
	 * Best improvement Search
	 * @return
	 */
	public JobSequence bestImprovementSearch() {
		log.trace("Entering bestImprovementSearch");
		JobSequence j=start.jobSeq;
		int bestToolSwitches=start.getToolSwitches();
		/*boolean improvement=true;
		 
	    while (!breakCriteria(improvement,1)) {
			int i=0;
			steps++;
			JobSequence n,bestSeq=j;
			improvement=false;
			log.trace("BEFORE INNER LOOP");
			// log.trace("j is:"+j.getSeqAsString()+" i is:"+i); // is in O(n) !!!
			while ((n=getNeighbor(j, i))!=null ) {
				visitedNeighbors++;
				HistoryMachine m=new HistoryMachine(n);
				if (m.getToolSwitches()<bestToolSwitches) {
					bestToolSwitches=m.getToolSwitches();
					bestSeq=m.jobSeq;
					improvement=true;
					// log.trace("IMPROVEMENT FOUND, better Sequence: " +bestSeq.getSeqAsString());
				}
				i++;
			}
			j=bestSeq;
		} */
		int l=getNeighborSize(start.jobSeq);
		for (int i=0;i<l;i++) {
			visitedNeighbors++;
			JobSequence j1=getNeighbor(start.jobSeq, i);
			if (j1==null) continue;
			int j1rs=(new HistoryMachine(j1)).getToolSwitches();
			if (j1rs<bestToolSwitches) {
				bestToolSwitches=j1rs;
				j=j1;
			}
		}
		steps++;
		return j;
	}
	
	
	/**
	 * random Search
	 * @param limit Anzahl der Versuche ohne Verbesserung bevor aufgegeben wird.
	 * @return
	 */
	public JobSequence randomSearch(int limit) {
		JobSequence j=start.jobSeq;
		int bestToolSwitches=start.getToolSwitches();
		boolean improvement=true;
		
		while (!breakCriteria(improvement,limit)) {
			JobSequence n;
			//getNeighbor(j, 1);
			steps++;
			int r=(int)(Math.random()*getNeighborSize(j));
			
			n=getNeighbor(j, r);
			HistoryMachine m=new HistoryMachine(n);
			visitedNeighbors++;
			improvement=false;
			if (m.getToolSwitches()<bestToolSwitches) {
					bestToolSwitches=m.getToolSwitches();
					j=m.jobSeq;
					improvement=true;
					continue;
			}
		}
		return j;
	}
	
	
	
	
}
